"""
https://leetcode.cn/problems/diameter-of-binary-tree/description/

543. 二叉树的直径
已解答
简单
相关标签
premium lock icon
相关企业
给你一棵二叉树的根节点，返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的 长度 由它们之间边数表示。

 

示例 1：


输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
示例 2：

输入：root = [1,2]
输出：1
 

提示：

树中节点数目在范围 [1, 104] 内
-100 <= Node.val <= 100

"""

from typing import Optional
from tree_node import TreeNode,build_tree_node

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    """
    设计二叉树，往往考虑父节点与左右子节点的关系
    每个树都必定有两种长，一种是题目中所述的直径，一种是从当前树的根节点的最长节点

    前者用max_len表示，后者用max_level表示
    则:
    if node:
        max_level(node)=max(max_level(node.left),max(node.right))+1
    else:
        max_level(node)=0
    
    temp_len=(node.left ? max_level(node.left)+1 : 0)+(node.right ? max_level(node.right)+1 : 0)
    max_len(node)=max(max_len(node.left),max_len(node.right),temp_len)

    """

    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        # 思想是动态规划。这里用了比较复杂的规划，实际可以简化，如max_len_map实际维护一个值即可

        node_level_map={}
        temp_len_map={}
        max_len_map={}

        def max_level(node):
            if not node:
                return 0
            nonlocal node_level_map
            if node in node_level_map:
                return node_level_map[node]
            if not node.left and not node.right:
                node_level_map[node]=0
                return 0
            ml=max(max_level(node.left),max_level(node.right))+1
            node_level_map[node]=ml
            return ml
            
        def temp_len(node):
            if not node:
                return 0
            nonlocal temp_len_map
            if node in temp_len_map:
                return temp_len_map[node]
            tl=(max_level(node.left)+1 if node.left else 0)+(max_level(node.right)+1 if node.right else 0)
            temp_len_map[node]=tl
            return tl
            
        def max_len(node):
            if not node:
                return 0
            nonlocal max_len_map
            if node in max_len_map:
                return max_len_map[node]
            else:
                # print(f'{node.val},{max_len(node.left)},{max_len(node.right)},{temp_len(node)}')
                return max(max_len(node.left),max_len(node.right),temp_len(node))
        
        return max_len(root)
    

if __name__=='__main__':
    arr=[1,2,3,4,5]
    tree_node=build_tree_node(arr)

    s=Solution()
    max_len=s.diameterOfBinaryTree(tree_node)
    print(max_len)